// https://www.lintcode.com/problem/n-queens-ii/

public class Solution {
    int ret;
    int limit;
    
    /**
     * @param n: The number of queens.
     * @return: The total number of distinct solutions.
     */
    public int totalNQueens(int n) {
        // write your code here
        ret = 0;
        limit = n;
        _totalNQueens(0, new ArrayList<List<Integer>>());
        return ret;
    }
    
    private void _totalNQueens(int row, List<List<Integer>> queens) {
        if (row == limit) {
            ++ret;
        } else {
            for (int col = 0; col < limit; ++col) {
                if (check(queens, row, col)) {
                    List<Integer> p = new ArrayList<>();
                    p.add(row);
                    p.add(col);
                    queens.add(p);
                    _totalNQueens(row + 1, queens);
                    queens.remove(queens.size() - 1);
                }
            }
        }
    }
    
    private boolean check(List<List<Integer>> queens, int row, int col) {
        for (List<Integer> queen : queens) {
            int r = queen.get(0);
            int c = queen.get(1);
            if ((c == col) || (Math.abs(r - row) == Math.abs(c - col))) {
                return false;
            }
        }
        return true;
    }
}